package com.leecode.base;

/**
 * @Author: yaoshubin
 * @Date: 2022-12-10 16:46
 * @description : 数组无序，返回其中一个局部最小就行
 * 如：[1,4,7,3,8,2,9]
 * 2 <8  & 2 < 9  ,2 就可以
 * 3 < 7 & 3<8 ,3 就可以
 * <p>
 * 特点：
 * 1）数组整体无序
 * 2）相邻元素都不等
 */
public class Index_05_二分法找局部最小 {

    public static void main(String[] args) {
        //int[] arr = {};
        //int[] arr = {3};
        int[] arr = {2, 9};
        //int[] arr = {10, 2, 9, 5, 7, 10, 12};
        int index = findRangeMinIndex(arr);
        System.out.println(index);
    }


    /**
     * 查找数组局部最小位置
     *
     * @param arr
     * @return
     */
    public static int findRangeMinIndex(int[] arr) {
        //处理边界
        if (arr == null || arr.length == 0) {
            return -1;
        }
        if (arr.length == 1) {
            return 0;
        }
        if (arr.length == 2) {
            if (arr[0] < arr[1]) {
                return 0;
            }
            return 1;
        }

        int left = 0;
        int right = arr.length - 1;
        int index = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            //巧了，中间就是
            if (arr[mid] < arr[mid + 1] && arr[mid] < arr[mid - 1]) {
                index = mid;
                return index;
            } else if (arr[mid] > arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return index;
    }

}
